package com.heima.algorithm.dynamicprogramming;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * 0-1背包问题   用动态规划解决
 * @author 勾新杰
 * @version 1.0
 * @date 2024/11/3 13:33
 */
public class KnapsackProblem {
    /*
     0-1 背包问题

     问题描述：
     1、n个物品都是固体，有重量和价值
     2、现在你要取走不超过 10g 的物品
     3、每次拿不拿或全拿，问能拿的最高价值是多少

     编号     名称         重量(g)       价值(元)
      0     钻戒一枚         1            1_000_000    // D
      1     黄金一枚         4            1600         // A
      2     红宝石戒指一枚    8            2400         // R
      3     白银一枚         5            30           // S

      0，1，2，3，4，5，6，7，8，9，10对应背包的容量
      0，1，2，3对应物品编号，第三行就是在前两行的基础上再去假如新的物品
      dp[i,j]表示前0-i个物品凑j容量的背包的价值最大值

          0   1   2   3   4   5   6   7   8   9   10
      0   0   D   D   D   D   D   D   D   D   D   D
      1   0   D   D   D   D   DA  DA  DA  DA  DA  DA
      2   0   D   D   D   D   DA  DA  DA  DA  DR  DR
      3   0   D   D   D   D   DA  DA  DA  DA  DR  DR

      1. 背包容量装不下，保持上一次的价值不变，也就是保留上一行的内容dp[i,j] = dp[i-1,j]
      2. 背包容量装得下：先把我自己装下，剩下的让用前面几种物品对应的剩下容量的最大价值
      dp[i,j] = max(dp[i-1][j], currItem[i].value + dp[i-1][j-currItem[i].weight])
     */

    /**
     * 物品类
     */
    public static class Item {
        int index;
        String name;
        double weight;
        double value;

        public Item() {
        }

        public Item(int index, String name, double weight, double value) {
            this.index = index;
            this.name = name;
            this.weight = weight;
            this.value = value;
        }

        public double valuePerWeight() {
            return value / weight;
        }

        public String name() {
            return name;
        }

        public double value() {
            return value;
        }

        @Override
        public String toString() {
            return "{" +
                    "name='" + name + '\'' +
                    ", weight=" + weight +
                    ", value=" + value +
                    '}';
        }
    }

    /**
     * 选择最大价值
     * @param itemList 物品列表
     * @param totalWeight 总重量
     * @return  选择结果的最大价值
     */
    public static double select(List<Item> itemList, double totalWeight) {
        // 1. 构建动态规划数组
        int rows = itemList.size();
        int columns = (int) (totalWeight + 1);
        double[][] dp = new double[rows][columns];
        // 2. 对dp数组第一行进行初始化
        for (int j = 0; j < columns; j++) {
            if (itemList.get(0).weight <= j){
                dp[0][j] = (int) itemList.get(0).value;
            }
        }
        print(dp);
        // 3. 逐行遍历dp数组，计算dp[i][j]
        for (int i = 1; i < rows; i++){
            Item currItem = itemList.get(i);
            for (int j = 0; j < columns; j++) {
                if (j < currItem.weight){
                    dp[i][j] = dp[i-1][j];
                }else {
                    dp[i][j] = Math.max(dp[i - 1][j], currItem.value + dp[i - 1][j - (int) currItem.weight]); // 前0 - i-1个物品去dou剩下的背包空间的最大价值
                }
            }
            print(dp);
        }
        // 4. 返回dp[rows-1][columns-1]
        return dp[rows - 1][columns - 1];
    }

    /**
     * 打印dp数组
     * @param dp dp数组
     */
    private static void print(double[][] dp) {
        for (double[] ints : dp) {
            System.out.print("[ ");
            for (double anInt : ints) {
                System.out.printf("%07d ", (int)anInt);
            }
            System.out.println("]");
        }
        System.out.println();
    }

    /**
     * 选择最大价值，dp降为一维数组
     * @param itemList 物品列表
     * @param totalWeight 总重量
     * @return  选择结果的最大价值
     */
    public static double select2(List<Item> itemList, double totalWeight) {
        // 1. 构建动态规划数组
        double[] dp = new double[(int) (totalWeight + 1)];
        // 2. 对dp数组第一行进行初始化
        for (int j = 0; j < dp.length; j++) {
            if (itemList.get(0).weight <= j){
                dp[j] = (int) itemList.get(0).value;
            }
        }
        System.out.println(Arrays.toString(dp));
        // 3. 逐行遍历dp数组，计算dp[i][j]
        for (int i = 1; i < itemList.size(); i++){
            Item currItem = itemList.get(i);
            for (int j = dp.length - 1; j > 0; j--) { // 要从右向左处理，因为选取当前物品后，剩余的容量肯定比当前背包总容量小，所以加的dp[(int)(j - currItem.weight)])肯定是上一轮的，而不是这轮已经处理过的
                if (currItem.weight <= j){
                    dp[j] = Math.max(dp[j], currItem.value + dp[(int)(j - currItem.weight)]); // 前0 - i-1个物品去dou剩下的背包空间的最大价值
                }
            }
            System.out.println(Arrays.toString(dp));
        }
        // 4. 返回dp数组右下角
        return dp[dp.length - 1];
    }

    public static void main(String[] args) {
        Item item1 = new Item(1, "钻戒一枚", 1, 1000000);
        Item item2 = new Item(2, "黄金一枚", 4, 1600);
        Item item3 = new Item(3, "红宝石戒指一枚", 8, 2400);
        Item item4 = new Item(4, "白银一枚", 5, 30);
        List<Item> itemList = new ArrayList<>();
        itemList.add(item1);
        itemList.add(item2);
        itemList.add(item3);
        itemList.add(item4);
        double totalWeight = 10;
        double result = select(itemList, totalWeight);
        System.out.println(result);
        result = select2(itemList, totalWeight);
        System.out.println(result);
    }
}
